Fitness Inheritance in the Bayesian Optimization Algorithm

Martin Pelikan¹ and Kumara Sastry²

¹Dept. of Math. and Computer Science, 320 CCB, University of Missouri at St. Louis, 8001 Natural Bridge Rd., St. Louis, MO 63121
pelikan@cs.umsl.edu

²Illinois Genetic Algorithms Laboratory, 107 TB, University of Illinois at Urbana-Champaign, 104 S. Mathews Ave. Urbana, IL 61801
kumara@illigal.ge.uiuc.edu

Abstract. This paper describes how fitness inheritance can be used to estimate fitness for a proportion of newly sampled candidate solutions in the Bayesian optimization algorithm (BOA). The goal of estimating fitness for some candidate solutions is to reduce the number of fitness evaluations for problems where fitness evaluation is expensive. Bayesian networks used in BOA to model promising solutions and generate the new ones are extended to allow not only for modeling and sampling candidate solutions, but also for estimating their fitness. The results indicate that fitness inheritance is a promising concept in BOA, because population-sizing requirements for building appropriate models of promising solutions lead to good fitness estimates even if only a small proportion of candidate solutions is evaluated using the actual fitness function. This can lead to a reduction of the number of actual fitness evaluations by a factor of 30 or more.

LNCS 3103, p. 48 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004